2018牛客网暑期多校 J-Different Integers 【离线+树状数组】

发表于 | 分类于

题目链接：戳这里

题意：t组样例，每组给n个数和q次查询，求每次查询中[1, l]和[r, n]中不同的数的个数

解题思路：

首先将数组×2，这样就可以由求[1, l] 和 [r, n]区间转化为求[r, n + l]区间。再把查询按照r从小到大排序，之所以这样排序，是为了一边修改前缀和，一边存储答案。

在更新点的时候，我们要用一个last[]数组记录当前数字出现的上一个位置，如果再次出现该数字，则

add(last[num[i]], -1);

add(i, 1) ;

这是用了差分数组的思路，把last[num[i]]的值-1，把i的值+1，最终得到的getsum(i)值是不变的，这样就减少了很多不必要的修改。

附ac代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&-x)
const int maxn = 4 * 1e5 + 10;
typedef int ll;
int nu[maxn];
int last[maxn];
int sum[maxn];
int n, q;
int res[maxn];
struct nod
{
    int id;
    int l;
    int r;
}qy[maxn];
bool cmp(nod a, nod b)
{
    return a.r < b.r;
}
void add(int *r, int pos, int v)
{
    while(pos <= n)
    {
        r[pos] += v;
        pos += lowbit(pos);
    }
}
int getsum(int *r, int pos)
{
    ll ans = 0;
  while(pos > 0)
  {
      ans += r[pos];
      pos -= lowbit(pos);
  }
  return ans;
}
int main()
{
 
    while(~scanf("%d %d", &n, &q))
    {
        memset(last, 0, sizeof(last));
        memset(sum, 0, sizeof(sum));
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", nu+i);
            nu[i + n] = nu[i];
        }
         
        int u, v;
        for(int i = 0; i < q; ++i)
        {
            scanf("%d %d", &u, &v);
            qy[i].id = i;
            qy[i].l = v;
            qy[i].r = n + u;
         //   printf("%d %d %d\n", qy[i].l, qy[i].r, i);
        }
        n <<= 1;
        sort(qy, qy + q, cmp);
        int len = 0;
        for(int i = 1; i <= n; ++i)
        {
       //         printf("%d %d i vis[nu[i]] \n", i, vis[nu[i]]);
                if(last[nu[i]]) add(sum, last[nu[i]], -1);
                add(sum, i, 1);
                last[nu[i]] = i;
                while(qy[len].r == i && len < q)
                {
//                  printf("%d %di %d %di", getsum(sum, qy[len].r), qy[len].r, getsum(sum, qy[len].l - 1), qy[len].l - 1);
                    res[qy[len].id] = getsum(sum, qy[len].r) - getsum(sum, qy[len].l - 1);
                    ++len;
                }
                if(len == q) break;
        }
        for(int i = 0; i < q; ++i)
            printf("%d\n", res[i]);
    }
    return 0;
}